Low power and Lossy Networks (LLNs), e.g., sensor networks, have a myriad of applications, such as Smart Grid and Smart Cities. Various challenges are presented with LLNs, such as lossy links, low bandwidth, battery operation, low memory and/or processing capability, etc. One example routing solution to LLN challenges is a protocol called Routing Protocol for LLNs or “RPL,” which is a distance vector routing protocol that builds a Destination Oriented Directed Acyclic Graph (DODAG, or simply DAG) in addition to a set of features to bound the control traffic, support local (and slow) repair, etc. The RPL architecture provides a flexible method by which each node performs DODAG discovery, construction, and maintenance.
There are many circumstances where it is desired to make use of what is referred to as “1+1” protection, where packets are duplicated and sent along diverse paths. The issue of computing diverse paths in a network greatly varies in complexity with the routing environment. For instance, in networks using a Link State routing protocol in a “flat” (non multi-area/level environment), known techniques such as the “Bhandari” algorithms can be used to simultaneously compute diverse paths. In such networks where the path spans multiple routing areas/level or AS, computing diverse paths becomes much more challenging, e.g., first computing one path, and then computing another path that is diverse from the first. Though useful in these environments, note that this two-step approach cannot guarantee finding diverse paths, and it is quite difficult to optimize, e.g., the sum of costs between the two paths, etc.
The issue then becomes even more difficult in networks using a distance vector routing protocol, such as RPL. For instance, each RPL instance is represented as a DODAG anchored at a root node, called an LBR (LLN Border Router). In a RPL “non-storing” mode, where packets may be source routed, it is possible to compute diverse paths from the DAG root after collecting the topology database, e.g., computing diverse paths in a manner similar to computing diverse paths in link-state routing environments understood in the art. However, computing diverse paths is much more difficult in the reverse direction, i.e., computing diverse paths from each node to the root, which is particularly exacerbated in constrained networks, e.g., LLNs.